package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/17 12:00
 * @description：https://leetcode-cn.com/problems/word-break/
 */
public class 单词拆分 {
    @Test
    public void test() {
        Solution solution = new Solution();
        List<String> list = new ArrayList<>();
        list.add("aaaa");
        list.add("aaa");
        System.out.println(solution.wordBreak("aaaaaaa", list));
    }

    class Solution {
        Trie root = new Trie();

        public boolean wordBreak(String s, List<String> wordDict) {
            for (String word : wordDict) {
                insert(word);
            }
            return dfs(s, 0, new boolean[s.length()]);
        }

        private boolean dfs(String s, int start, boolean[] isVisited) {
            if (s.length() == start) return true;
            if (isVisited[start]) return false;
            isVisited[start] = true;
            Trie node = root;
            for (int i = start; i < s.length(); i++) {
                int index = s.charAt(i) - 'a';
                node = node.children[index];
                if (node == null) return false;
                if (node.isEnd) {
                    if (dfs(s, i + 1, isVisited)) {
                        return true;
                    }
                }
            }
            return false;
        }

        public void insert(String word) {
            Trie node = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }
    }

    class Trie {
        boolean isEnd;
        public Trie[] children;

        public Trie() {
            isEnd = false;
            children = new Trie[26];
        }
    }
}
